package cn.edu.jxau.util;

import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * 利用链表实现栈
 * 1.每项操作的用时都和集合大小无关
 * 2.空间需求总是不超过集合大小乘以一个常数
 * 3.无需扩容，所以所有操作所需的时间总是和集合大小无关
 * @author 付大石
 */
public class LinkedStack<T> extends Stack<T> {

    /**
     * 栈顶指针
     */
    private Node<T> first;

    /**
     * 栈中元素数量
     */
    private int size;

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {

            private Node<T> cursor = first;

            @Override
            public boolean hasNext() {
                return cursor != null;
            }

            @Override
            public T next() {

                if (!hasNext()) {
                    throw new NoSuchElementException("迭代器所处位置无元素");
                }
                T item = cursor.item;
                cursor = cursor.next;
                return item;
            }
        };
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public T peek() {

        if (first == null) {
            return null;
        } else {
            return first.item;
        }
    }

    @Override
    public T pop() {

        if (first == null) {
            return null;
        }
        T item = peek();
        first = first.next;
        size--;
        return item;
    }

    @Override
    public void push(T item) {

        Node<T> oldFirst = first;
        first = new Node<>(item);
        first.next = oldFirst;
        size++;
    }

    @Override
    public String toString() {

        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("stack size=").append(size).append("\t");
        stringBuilder.append("[");
        if (size == 0) {
            stringBuilder.append("]");
        } else {
            Node<T> cursor = first;
            while (cursor != null) {
                stringBuilder.append(cursor.item).append(",");
                cursor = cursor.next;
            }
            stringBuilder.deleteCharAt(stringBuilder.length() - 1).append("]");
        }
        return stringBuilder.toString();
    }
    
    private class Node<T> {
        private T item;
        private Node<T> next;

        public Node() {

        }

        public Node(T item) {
            this.item = item;
        }
    }
}
